ML (programozási nyelv)

ML
Paradigma	procedurális programozás funkcionális programozás imperatív programozás
Megjelent	1973
Tervező	Robin Milner
Fejlesztő	Robin Milner
Hatással volt rá	ISWIM

Az ML (Meta Language) egy általános célú funkcionális programozási nyelv. A polimorf Hindley–Milner típusrendszer használatáról ismert, amely automatikusan típusokat rendel a legtöbb kifejezéshez anélkül, hogy kifejezett típushozzárendelést igényelne, és biztosítja a típusbiztonságot – hivatalosan bebizonyították, hogy a jól megírt ML program nem okoz futásidejű hibákat. Az ML biztosítja a mintafelismerést a függvényargumentumok, a szemétgyűjtés, az imperatív programozás, az érték szerinti paraméterátadás és a függvényátalakítások (currying) számára. Gyakran használják a programozási nyelvek kutatásában, és egyike azon kevés nyelveknek, amelyeket formális szemantika segítségével teljesen meg lehet határozni és ellenőrizni. Típusai és mintafelismerése alkalmassá teszik arra, hogy más formális nyelvekhez is alkalmasak legyenek, például fordítók írásához, automatikus tételbizonyításhoz és formális ellenőrzéshez.

Áttekintés

Az ML jellegzetességei közé tartoznak az érték szerinti hívások (call-by-value) kiértékelési stratégiái, az elsőosztályú függvények, automatikus memóriakezelés szemétgyűjtés útján, paraméteres polimorfizmus, statikus tipizálás, típuskövetkeztetés, kompozit adattípusok, mintafelismerés, kivételkezelés. Az ML statikus hatóköröket használ.

Az ML nem nevezhető pusztán funkcionális nyelvnek, mert bár ösztönzi a funkcionális programozást, mégis megengedi a mellékhatásokat (mint például a Lisp, de különbözik a tisztán funkcionális nyelvektől, mint a Haskell). A legtöbb programozási nyelvhez hasonlóan az ML is mohó kiértékelést alkalmaz, ami azt jelenti, hogy minden alkifejezést kiértékel, bár lusta kiértékelés is elérhető bezárások (closure) használatával. Így végtelen csatornák használhatók, akárcsak Haskellben, bár kifejezésük közvetett.

Az ML-nek szembetűnő előnyeit vannak a nyelvek tervezésében és kezelésében (fordítók, elemzők, tételbizonyítások), bár ez egy általános célú nyelv, amelyet használnak például a bioinformatikában és a pénzügyi rendszerekben is.

Az ML-t Robin Milner és mások fejlesztették ki az 1970-es évek elején az Edinburgh-i Egyetemen, szintaxisát az ISWIM ihlette. Történelmileg az ML-t úgy tervezték, hogy bizonyítási taktikát dolgozzon ki az LCF tételbizonyítóban (amelynek pplambda nyelve – az elsőrendű logikai számítás és az egyszerűen tipizált polimorf lambda-számítás kombinációja – volt az ML metanyelve).

Ma több nyelv van az ML családban; a három legkiemelkedőbb a Standard ML (SML), az OCaml és az F#. Az ML ötletei számos más nyelvet is befolyásoltak, például Haskell, Cyclone, Nemerle, ATS és Elm.

Példák

A következő példák a Standard ML szintaxisát használják. Más ML dialektusok, például az OCaml és az F#, kis mértékben különböznek egymástól.

Faktoriális

A faktoriális függvény tiszta ML-ként kifejezve:

fun fac (0 : int) : int = 1
  | fac (n : int) : int = n * fac (n - 1)

Ez rekurzív függvényre bomlik, egyetlen végződéssel. Hasonló a matematikai tankönyvek faktoriálisának leírásához. Az ML kód hasonló a matematikai kifejezésekhez szintaxisában és funkciójában.

A megadott definíció egy része opcionális, és a típusokat írja le. Az E : t jelentése, hogy az E kifejezés típusa t. Például az n paraméter egész szám (int), és a fac (n : int) szintén az. A fac függvény tehát egész számot fogad el bevitelként, és egész számot térít vissza. A típuskövetkeztetésnek köszönhetően ez elhanyagolható, a példa pedig a következőképpen írható:

fun fac 0 = 1
  | fac n = n * fac (n - 1)

Ez a függvény a mintafelismerésre is támaszkodik, amely az ML fontos része. Megjegyzendő, hogy a függvény paraméterei nem feltétlenül kell zárójelben legyenek, elég őket szóközökkel elválasztani. Ha a függvény paramétere 0, az eredmény 1 lesz. Minden más esetben a második sor fut. Ez rekurzív, és addig hajtja végre a függvényt, amíg el nem éri az alapesetet.

Nincsen garancia arra, hogy a faktoriális függvény ezen megvalósítása befejeződik, mert egy negatív paraméter végtelen hívásláncot eredményez. Egy robusztusabb kivitelezés ellenőrzi, hogy a paraméter negatív-e:

fun fact n = let
  fun fac 0 = 1
    | fac n = n * fac (n - 1)
  in
    if (n < 0) then raise Domain else fac n
  end

A problémás eset (amikor n negatív) az ML kivételrendszerének használatát mutatja be.

A funkció tovább javítható a belső ciklus szubrutinként való átírásával, ezáltal a hívási verem nem növekedik a hívások számával. Ezt úgy érhetjük el, hogy egy akkumulátor paramétert helyezünk a belső ciklusba:

fun fact n = let
  fun fac 0 acc = acc
    | fac n acc = fac (n - 1) (n * acc)
  in
    if (n < 0) then raise Domain else fac n 1
  end

Lista megfordítása

A következő függvény megfordítja a lista elemeit, vagyis egy új listát ad vissza, amelynek elemei fordított sorrendben vannak az eredeti listához képest.

fun reverse [] = []
  | reverse (x :: xs) = (reverse xs) @ [x]

Ez a fordított megvalósítás, bár helytálló és érthető, nem hatékony, mivel négyzetes időkomplexitást igényel. A függvény átírható lineáris időigényűre:

fun 'a reverse xs : 'a list = List.foldl (op ::) [] xs

Ez a függvény a paraméter-polimorfizmus figyelemre méltó példája; bármely típusú elemek lehetnek a listában elfogadhat, és hasonló típusú elemeket térít vissza.

Modulok

A modulok az ML rendszerei nagy programok és könyvtárak felépítéséhez. A modul egy aláírásfájlból és egy vagy több struktúrafájlból áll. Az aláírásfájl meghatározza a kivitelezendő API-t (mint például egy C header vagy Java class fájl), a struktúra pedig implementálja az aláírásokat (mint ahogy egy C forrásfájl vagy Java osztályfájl). Például a következők meghatároznak egy Arithmetic aláírást egy Rational implementációt:

signature ARITH =
sig
        type t
        val zero : t
        val succ : t -> t
        val sum : t * t -> t
end

structure Rational : ARITH =
struct
        datatype t = Rat of int * int
        val zero = Rat (0, 1)
        fun succ (Rat (a, b)) = Rat (a + b, b)
        fun sum (Rat (a, b), Rat (c, d)) = Rat (a * d + c * b , b * d)
end

Ezeket a "use" paranccsal importálják az értelmezőprogramba. Az interakció csupán az aláírásfájlon keresztül megengedett, például nem hozható létre direkt egy Rat adatobjektum e kódon keresztül. A structure blokk kívülről elrejti az implementáció minden részletét.

Az ML standard könyvtárai modulokként vannak implementálva.

Fordítás

Ez a szócikk részben vagy egészben a ML (programming language) című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További irodalom

• The Definition of Standard ML, Robin Milner, Mads Tofte, Robert Harper, MIT Press 1990; (revised edition adds author David MacQueen), MIT Press 1997, ISBN 0-262-63181-4.
• Commentary on Standard ML, Robin Milner, Mads Tofte, MIT Press 1997, ISBN 0-262-63137-7.
• ML for the Working Programmer, Lawrence Paulson, Cambridge University Press 1991, 1996, ISBN 0-521-57050-6.
• Harper, Robert. Programming in Standard ML. Carnegie Mellon University (2011) 
• Elements of ML Programming, Jeffrey D. Ullman, Prentice-Hall 1994, 1998, ISBN 0-13-790387-1.

Külső hivatkozások

• New Jersey standard ML, másik népszerű megvalósítás
• F#, egy ML megvalósítás a Microsoft segítségével NET Framework
• MLton, egy egész program, amely optimalizálja a Standard ML fordítót
• Successor-ML vagy sML
• CakeML, az ML read-eval-print ciklusváltozata, hivatalosan ellenőrzött futással és fordítással az assemblerhez